package 剑指专题.排序;


/*
 * Author：江松
 * Date：2023/3/31 20:36
 *
 数组中的逆序对：
 1，归并排序思想,排序区分i肯定比j小，那么每放入i，就与已经放入的j构成逆序对
 */

public class Main2 {
    private static final int mod=1000000007;
    private int tmp[];
    private int res;

    public void mergeSort(int []a,int l,int r){
        if(l>=r)return;
        int mid=l+r>>1;
        mergeSort(a,l,mid);
        mergeSort(a,mid+1,r);

        int i=l,j=mid+1;
        int cnt=0;
        while(i<=mid&&j<=r){
            if(a[i]<a[j]){
                tmp[cnt++]=a[i++];
                res=(res+j-mid-1)%mod;
            }else{
                tmp[cnt++]=a[j++];
            }
        }
        while(i<=mid){
            tmp[cnt++]=a[i++];
            res=(res+r-mid)%mod;
        }
        while(j<=r){
            tmp[cnt++]=a[j++];
        }

        for(int k=0;k<cnt;++k){
            a[l+k]=tmp[k];
        }
    }

    public int InversePairs(int [] array) {
        if(array==null||array.length<1)return 0;
        tmp=new int[array.length];
        mergeSort(array,0,array.length-1);
        return res;
    }
}
